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

DOI10.1007/s00453-009-9380-6zbMath1217.05064OpenAlexW2082479932MaRDI QIDQ547303

Giuseppe Di Battista, Maurizio Patrignani, Patrizio Angelini

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

planar graphplanar embeddingminimum depthtriconnected components

Mathematics Subject Classification ID

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

Related Items (6)

Planar Embeddings with Small and Uniform Faces ⋮ Topological morphing of planar graphs ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ Unnamed Item ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings ⋮ TESTING MUTUAL DUALITY OF PLANAR GRAPHS

Cites Work

• Unnamed Item
• On the complexity of embedding planar graphs to minimize certain distance measures
• Graph minors. III. Planar tree-width
• Undirected single-source shortest paths with positive integer weights in linear time
• Determining the Smallest k Such That G Is k-Outerplanar
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Approximation algorithms for NP-complete problems on planar graphs
• On-Line Planarity Testing
• Computing Radial Drawings on the Minimum Number of Circles
• Graph Drawing

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