Drawings of planar graphs with few slopes and segments

DOI10.1016/j.comgeo.2006.09.002zbMath1129.65010arXivmath/0606450OpenAlexW3103264504MaRDI QIDQ2385699

David R. Wood, David Eppstein, Matthew Suderman, Vida Dujmović

Publication date: 12 October 2007

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

graph drawingcanonical decompositionouterplanar graphstraight-line drawingslopesegment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (41)

Upward Planar Drawings with Three and More Slopes ⋮ Drawing plane triangulations with few segments ⋮ Planar drawings with few slopes of Halin graphs and nested pseudotrees ⋮ Geometric representation of cubic graphs with four directions ⋮ Minimum-segment convex drawings of 3-connected cubic plane graphs ⋮ PROXIMITY DRAWINGS OF HIGH-DEGREE TREES ⋮ Graph drawings with few slopes ⋮ Upward planar drawings with three and more slopes ⋮ The planar slope number of planar partial 3-trees of bounded degree ⋮ Upward planar drawings with two slopes ⋮ Orthogonal cartograms with at most 12 corners per face ⋮ Drawing Planar Graphs with Few Geometric Primitives ⋮ Universal slope sets for 1-bend planar drawings ⋮ Drawing Cubic Graphs with the Four Basic Slopes ⋮ The segment number: algorithms and universal lower bounds for some classes of planar graphs ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Drawing subcubic planar graphs with four slopes and optimal angular resolution ⋮ An annotated review on graph drawing and its applications ⋮ Drawing Graphs on Few Lines and Few Planes ⋮ Line and plane cover numbers revisited ⋮ Drawing planar graphs with few segments on a polynomial grid ⋮ Variants of the segment number of a graph ⋮ Drawing partial 2-trees with few slopes ⋮ Outerplanar graph drawings with few slopes ⋮ Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments ⋮ Experimental Analysis of the Accessibility of Drawings with Few Segments ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ Every large point set contains many collinear points or an empty pentagon ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ Visibility drawings of plane 3-trees with minimum area ⋮ Drawing cubic graphs with at most five slopes ⋮ Universal slope sets for upward planar drawings ⋮ Experimental Analysis of the Accessibility of Drawings with Few Segments ⋮ Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three ⋮ Level-planar drawings with few slopes ⋮ Level-planar drawings with few slopes ⋮ Drawing graphs as spanners ⋮ Drawing Graphs on Few Circles and Few Spheres ⋮ A note on isosceles planar graph drawing ⋮ Intersections and circuits in sets of line segments ⋮ Some results on point visibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• How to draw a planar graph on a grid
• A linear algorithm to find a rectangular dual of a planar triangulated graph
• A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
• On grid intersection graphs
• Rectangular grid drawings of plane graphs
• A left-first search algorithm for planar graphs
• Drawing planar graphs using the canonical ordering
• Graph drawings with few slopes
• Bounded-degree graphs have arbitrarily large geometric thickness
• Bounded-degree graphs can have arbitrarily large slope numbers
• Bemerkungen zum Vierfarbenproblem
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph
• A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs
• Box-Rectangular Drawings of Plane Graphs
• Triangle-Free Planar Graphs and Segment Intersection Graphs
• Rectangular drawings of planar graphs
• Graph Drawing
• On Diagrams Representing Maps
• Graph Drawing
• Rectangular drawings of plane graphs without designated corners

This page was built for publication: Drawings of planar graphs with few slopes and segments