Graph Drawing:

On 2-visibility drawing, we give an O(n)-time algorithm that produces an $n*\frac{2}{3}n$ 2-visibility drawing for any n-node planar graph. Fößmeier, Kant, and Kaufmann gave an $O(n)$-time algorithm that computes an $x\times y$ 2-visibility drawing of any $n$-node planar graph, where $x+y\leq 2n$. Moreover, they showed a planar graph whose $x\times y$ 2-visibility drawing has to satisfy $x+y\geq \frac{5}{3}n$, $x\geq \frac{2}{3}n$, and $y\geq\frac{2}{3}n$. According to this lower bound, the 2-visibility drawing produced for plane graph by our algorithm is optimal.

On maximum symmetric subgraphs, we address the problem of deriving a maximum symmetric graph from the input n-node graph G by three types of basic graph operations: (1) node extraction, (2) edge deletion, and (3) edge contraction. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show how the operation types affect the tractability of this problem when G is a plane graph, an ordered tree, and an unordered tree. For the intractable case that G is an unordered tree, we give an O(log n)-approximation algorithm that derives a symmetric tree from G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem.