The complexity of drawing a graph in a polygonal region
From MaRDI portal
Publication:1725774
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
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