Optimal polygonal representation of planar graphs

DOI10.1007/s00453-011-9525-2zbMath1239.05126arXiv1104.1482OpenAlexW2176056854MaRDI QIDQ2429359

Yifan Hu, Christian A. Duncan, Stephen G. Kobourov, Michael Kaufmann, Emden R. Gansner

Publication date: 26 April 2012

Published in: Algorithmica, LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.1482

zbMATH Keywords

planar graphsgraph drawingcontact graphspolygonal drawings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Simple algorithms for partial and simultaneous rectangular duals with given contact orientations ⋮ Contact Graphs of Circular Arcs ⋮ A New Approach for Contact Graph Representations and Its Applications ⋮ Area-universal drawings of biconnected outerplane graphs ⋮ Linear-time algorithms for hole-free rectilinear proportional contact graph representations ⋮ Extending partial representations of rectangular duals with given contact orientations ⋮ Computing cartograms with optimal complexity ⋮ Proportional Contact Representations of Planar Graphs ⋮ Homothetic triangle representations of planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for drawing a planar graph on a grid
• How to draw a planar graph on a grid
• A theory of rectangular dual graphs
• On rectilinear duals for vertex-weighted plane graphs
• Image partition regularity near zero
• Interval representations of planar graphs
• Classes and recognition of curve contact graphs
• The rectangle of influence drawability problem
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Drawing planar graphs using the canonical ordering
• On Touching Triangle Graphs
• Rectangular dualization and rectangular dissections
• Efficient Planarity Testing
• On Floor-Plan of Plane Graphs
• On Finding the Rectangular Duals of Planar Triangular Graphs
• On Triangle Contact Graphs
• Compact floor-planning via orderly spanning trees
• Rectangular drawings of planar graphs
• Sliceable Floorplanning by Graph Dualization
• Rectangular layouts and contact graphs
• Proportional Contact Representations of Planar Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)