Drawing planar graphs with few geometric primitives

DOI10.1007/978-3-319-68705-6_24MaRDI QIDQ1687929zbMATH OpenOpenAlexFDO

Authors Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans, André Schulz

Publication date 4 January 2018

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We define the emph{visual complexity} of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw a path with an arbitrary number of edges). Let $n$ denote the number of vertices of a graph. We show that trees can be drawn with $3n/4$ straight-line segments on a polynomial grid, and with $n/2$ straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with $(8n-17)/3$ segments on an $O(n)imesO(n^2)$ grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with $3n/2$ edges on an $O(n)imesO(n^2)$ grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only $(5n-11)/3$ arcs. This is significantly smaller than the lower bound of $2n$ for line segments for a nontrivial graph class.

Recommendations

• Drawing planar graphs with few geometric primitives
• Drawing graphs with few arcs
• Drawings of planar graphs with few slopes and segments
• Drawing Graphs with Few Arcs
• Drawing planar graphs using the canonical ordering

Cited in

(22)

• Drawing plane triangulations with few segments
• Drawing planar graphs with few segments on a polynomial grid
• Variants of the segment number of a graph
• Planar polyline drawings via graph transformations
• Drawing graphs on few circles and few spheres
• Rook-Drawing for Plane Graphs
• Drawing Graphs on Few Lines and Few Planes
• Complexity measures for mosaic drawings
• Drawing planar cubic 3-connected graphs with few segments: algorithms \& experiments
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• Pointed drawings of planar graphs
• Drawing planar graphs with few geometric primitives
• Experimental analysis of the accessibility of drawings with few segments
• Drawing planar graphs with many collinear vertices
• Drawing planar graphs with prescribed face areas
• Experimental analysis of the accessibility of drawings with few segments
• Drawing graphs on few circles and few spheres
• Drawing graphs on few lines and few planes
• Simplifying Non-Simple Fan-Planar Drawings
• Drawing graphs with few arcs
• Drawing Planar Graphs with Reduced Height
• An annotated review on graph drawing and its applications

This page was built for publication: Drawing planar graphs with few geometric primitives

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