The complexity of drawing a graph in a polygonal region

DOI10.1007/978-3-030-04414-5_28OpenAlexW2963616416MaRDI QIDQ1725774

Tillmann Miltzow, Debajyoti Mondal, Anna Lubiw

Publication date: 15 February 2019

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

Mathematics Subject Classification ID

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

Related Items

The Complexity of Drawing a Graph in a Polygonal Region ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ One-bend drawings of outerplanar graphs inside simple polygons ⋮ Smoothing the Gap Between NP and ER ⋮ On compatible triangulations with a minimum number of Steiner points ⋮ Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality ⋮ The complexity of drawing a graph in a polygonal region ⋮ \(\beta\)-stars or on extending a drawing of a connected subgraph ⋮ Polygon simplification by minimizing convex corners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extending convex partial drawings of graphs
• Fixed points, Nash equilibria, and the existential theory of the reals
• Convex drawings of graphs with non-convex boundary constraints
• Minimum-link watchman tours
• Some provably hard crossing number problems
• Minimum-link paths among obstacles in the plane
• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• Intersection graphs of segments
• \(\forall\exists\mathbb {R}\)-completeness and area-universality
• The complexity of drawing a graph in a polygonal region
• Integer realizations of disk and segment graphs
• Discrete one-forms on meshes and applications to 3D mesh parameterization
• A linear time algorithm for minimum link paths inside a simple polygon
• Convex Representations of Graphs
• The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
• Complexity of Some Geometric and Topological Problems
• Irrational Guards are Sometimes Needed
• Testing Planarity of Partially Embedded Graphs
• The art gallery problem is ∃ ℝ-complete
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• How to Draw a Graph
• Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
• Graph Drawing
• Drawing Partially Embedded and Simultaneously Planar Graphs