Straight-Line Drawability of a Planar Graph Plus an Edge

DOI10.1007/978-3-319-21840-3_25MaRDI QIDQ3449828zbMATH OpenOpenAlexWikidataFDO

Authors Peter Eades, Seok-Hee Hong, Giuseppe Liotta, Naoki Katoh, Sheung-Hung Poon

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.

Recommendations

• An algorithm for straight-line drawing of planar graphs
• Straight line representations of planar graphs
• On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
• scientific article; zbMATH DE number 821869
• Density of straight-line 1-planar graph drawings
• Straight-line grid drawings of 3-connected 1-planar graphs
• On the Planarity of Generalized Line Graphs
• Strictly convex drawings of planar graphs
• Strictly convex drawings of planar graphs
• scientific article; zbMATH DE number 1090018

Cites work

• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Area requirement and symmetry display of planar upward drawings
• Convex drawings of graphs with non-convex boundary constraints
• Fáry's theorem for 1-planar graphs
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3885930 (Why is no real title available?)
• Inserting an edge into a planar graph
• Level Planar Embedding in Linear Time
• Planar orientations with low out-degree and compaction of adjacency matrices
• Rectilinear drawings of graphs
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs

Cited in

(13)

• A linear-time algorithm for testing full outer-2-planarity
• Polyline drawings with topological constraints
• Straight-line grid drawings of 3-connected 1-planar graphs
• Fáry's theorem for 1-planar graphs
• Picking planar edges; or, drawing a graph with a planar subgraph
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Beyond planar graphs: introduction
• Algorithms for 1-Planar Graphs
• Polyline Drawings with Topological Constraints
• How to draw a planarization
• Inserting an edge into a geometric embedding
• Inserting an edge into a geometric embedding
• An annotated review on graph drawing and its applications

This page was built for publication: Straight-Line Drawability of a Planar Graph Plus an Edge

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