On the complexity of embedding planar graphs to minimize certain distance measures
From MaRDI portal
Publication:582079
DOI10.1007/BF01840379zbMath0689.68044MaRDI QIDQ582079
Clyde l. Monma, Bienstock, Daniel
Publication date: 1990
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (18)
An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ Topological morphing of planar graphs ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ A Note on the Minimum H-Subgraph Edge Deletion ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Homotopy height, grid-major height and graph-drawing height ⋮ Unnamed Item ⋮ A note on the complexity of matching patterns with variables ⋮ Polynomially solvable special cases of the Steiner problem in planar networks ⋮ On the parameterized complexity of layered graph drawing ⋮ Disjoint paths in sparse graphs ⋮ Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time ⋮ A tighter insertion-based approximation of the crossing number ⋮ Approximating the minimum hub cover problem on planar graphs ⋮ On exteriority notions in book embeddings and treewidth ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ TESTING MUTUAL DUALITY OF PLANAR GRAPHS
Cites Work
This page was built for publication: On the complexity of embedding planar graphs to minimize certain distance measures
