CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS

DOI10.1142/S0129054105002905zbMath1096.68122OpenAlexW3021406699MaRDI QIDQ4675884

MacHiko Azuma, Kazuyuki Miura, Takao Nishizeki

Publication date: 6 May 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105002905

zbMATH Keywords

graph encodingconvex grid drawingsfloor-planningsstraight-line grid drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

On simultaneous straight-line grid embedding of a planar graph and its dual ⋮ Acyclic colorings of graph subdivisions revisited ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Good spanning trees in graph drawing ⋮ On Representation of Planar Graphs by Segments ⋮ Drawing planar graphs with few segments on a polynomial grid ⋮ CONVEX DRAWINGS OF INTERNALLY TRICONNECTED PLANE GRAPHS ON O(n²) GRIDS

Cites Work

• A linear-time algorithm for drawing a planar graph on a grid
• How to draw a planar graph on a grid
• Grid embedding of 4-connected plane graphs
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Drawing planar graphs using the canonical ordering
• Compact floor-planning via orderly spanning trees
• Convex drawings of planar graphs and the order dimension of 3-polytopes

This page was built for publication: CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS