Finding a minimum-depth embedding of a planar graph in O(n^4) time

DOI10.1007/S00453-009-9380-6MaRDI QIDQ547303zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Giuseppe Di Battista, Maurizio Patrignani

Publication date 1 July 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9380-6

zbMATH Keywords

minimum depthplanar embeddingplanar graphtriconnected components

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Computing a Minimum-Depth Planar Graph Embedding in O(n 4) Time
• scientific article; zbMATH DE number 1670673
• Graph Drawing
• On the complexity of embedding planar graphs to minimize certain distance measures
• Graph Drawing

Cites work

• Approximation algorithms for NP-complete problems on planar graphs
• Computing Radial Drawings on the Minimum Number of Circles
• Determining the Smallest k Such That G Is k-Outerplanar
• Graph Drawing
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 1670673 (Why is no real title available?)
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On the complexity of embedding planar graphs to minimize certain distance measures
• On-Line Planarity Testing
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(11)

• An SPQR-tree-like embedding representation for upward planarity
• Planar embeddings with small and uniform faces
• Determining the Smallest k Such That G Is k-Outerplanar
• Computing a Minimum-Depth Planar Graph Embedding in O(n 4) Time
• Topological morphing of planar graphs
• Approximation Algorithms for Facial Cycles in Planar Embeddings
• Testing mutual duality of planar graphs
• On the complexity of embedding planar graphs to minimize certain distance measures
• Graph Drawing
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Ranking and unranking of the planar embeddings of a planar graph

This page was built for publication: Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q547303)