Abstract Let $G$ be a vertex-weighted connected graph of $n$ vertices and let $T$ be a spanning tree of $G$. We call $T$ a maximum weighted internal spanning tree of $G$ if the sum of the weights of the internal vertices of $T$ is the maximum over all spanning trees of $G$. The maximum weighted internal spanning tree (MaxwIST) problem asks to find such a spanning tree $T$ of $G$. The problem is NP-hard. We give an $O(dn)$ time approximation algorithm for $d$-regular graphs of $n=|V|$ vertices that computes a spanning tree with total weight of the internal vertices is at least $\frac{\beta _{d}}{\beta _{d} +d-2} - \epsilon $ of the total weight of all the vertices of the graph for any $\epsilon>0$, where $\beta _{d} = (d-1)H_{d-1}$, and $H_{d-1} = \sum _{i=1}^{d-1} i^{-1}$ is the $(d-1)$th harmonic number. For every $d \geq 3$ and $n_{0} \geq 1$, we show the construction of a $d$-regular graph of at least $n_{0}$ vertices, such that for any of its spanning trees, $\frac{w(I)}{w(V)}\le \frac{d}{d+1}$ holds. We give an $O(dn)$ time approximation algorithm for subdivisions of $d$-regular graphs, where the ratio of the internal weight of the spanning tree with the total vertex weight of the graph is at least $\frac{d-1}{2d-3} - \epsilon $ for $\epsilon>0$. We extend our study to $x$-subdivisions of Hamiltonian and hypoHamiltonian graphs, where each edge of the original Hamiltonian or hypoHamiltonian graph has been subdivided at least $x$ times. For those two graph classes, we show that there exists a spanning tree with internal vertex weight at least $1-\frac{2}{x-1}$ of the total vertex weight of the graph. Furthermore, we give $O(n)$ time algorithm for $x$-subdivisions of biconnected outerplanar graphs and $4$-connected planar graphs to achieve the above bound.

Abstract A graph $G = (V,E)$ is called a pairwise compatibility graph (PCG) if it admits a tuple $(T, d_{min},d_{max})$ of an edge-weighted tree $T$ of non-negative edge weights with leaf set $L$, two non-negative real numbers $d_{min} \leq d_{max}$ such that each vertex $u^{\prime} \in V$ represents a leaf $u \in L$ and $G$ has an edge $(u^{\prime},v^{\prime}) \in E$ if and only if the distance between the two leaves $u$ and $v$ in the tree $T$ lies within interval $[d_{min}, d_{max}]$. It has been proven that not all graphs are PCGs. A graph $G$ is called a $k$-interval PCG if there exists an edge-weighted tree $T$ and $k$ mutually exclusive intervals of non-negative real numbers such that there is an edge between two vertices in $G$ if and only if the distance between their corresponding leaves in $T$ lies within any of the $k$ intervals. It is known that every graph $G$ is a $k$-interval PCG for $k=|E|$, where $E$ is the set of edges of $G$. It is thus interesting to know the smallest value of $k$ for which $G$ is a $k$-interval PCG. In this paper, we show that grid graphs and a subclass of $3$D grid graphs are $2$-interval PCGs.

Abstract In a box‐drawing of a rooted tree, each node is drawn by a rectangular box of prescribed size, no two boxes overlap each other, all boxes corresponding to siblings of the tree have the same x‐coordinate at their left sides, and a parent node is drawn at a given distance apart from its first child. A box drawing of a tree is compact if it attains the minimum possible rectangular area enclosing the drawing. We give a linear‐time algorithm for finding a compact box‐drawing of a tree. A known algorithm does not always find a compact box‐drawing and takes time O(n2) if a tree has n nodes. © 2003 Wiley Periodicals, Inc.