Extending convex partial drawings of graphs

DOI10.1007/S00453-015-0018-6MaRDI QIDQ334920zbMATH OpenOpenAlexFDO

Authors Tamara Mchedlidze, Martin Nöllenburg, Ignaz Rutter

Publication date 1 November 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0018-6

zbMATH Keywords

linear-time algorithmconvex shapeextension of a partial drawingfixed cyclefixed inner facestraight-line drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Drawing planar graphs with a prescribed inner face
• Testing planarity of partially embedded graphs
• Graph Drawing
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• -stars or on extending a drawing of a connected subgraph

Cites work

• A Kuratowski-type theorem for planarity of partially embedded graphs
• Convex drawings of graphs with non-convex boundary constraints
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Drawing partially embedded and simultaneously planar graphs
• Drawing planar graphs with a prescribed inner face
• Embedding planar graphs at fixed vertex locations
• Generating rooted triangulations without repetitions
• How to Draw a Graph
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Planar drawings of higher-genus graphs
• Testing planarity of partially embedded graphs
• The Vertex-Disjoint Menger Problem in Planar Graphs

Cited in

(20)

• -stars or on extending a drawing of a connected subgraph
• The complexity of drawing a graph in a polygonal region
• scientific article; zbMATH DE number 1156579 (Why is no real title available?)
• Level-planar drawings with few slopes
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• Beyond Clustered Planar Graphs
• Extending partial orthogonal drawings
• How to draw a planarization
• On-line convex planarity testing
• One-bend drawings of outerplanar graphs inside simple polygons
• Extending orthogonal planar graph drawings is fixed-parameter tractable
• The complexity of drawing a graph in a polygonal region
• Graph Drawing
• Level-planar drawings with few slopes
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Inserting one edge into a simple drawing is hard
• Incremental convex planarity testing
• Drawing planar graphs with a prescribed inner face
• Testing planarity of partially embedded graphs
• Extending simple drawings

This page was built for publication: Extending convex partial drawings of graphs

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