The Complexity of Drawing a Graph in a Polygonal Region
From MaRDI portal
Publication:5050006
DOI10.7155/jgaa.00602zbMath1499.68147OpenAlexW2788640963MaRDI QIDQ5050006
Debajyoti Mondal, Anna Lubiw, Tillmann Miltzow
Publication date: 14 November 2022
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00602
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extending convex partial drawings of graphs
- Sphere and dot product representations 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
- The complexity of drawing a graph in a polygonal region
- Mnëv's universality theorem revisited
- Integer realizations of disk and segment graphs
- A Kuratowski-type theorem for planarity of partially embedded graphs
- Simple realizability of complete abstract topological graphs simplified
- Variants of the segment number of a graph
- Discrete one-forms on meshes and applications to 3D mesh parameterization
- Thirty Essays on Geometric Graph Theory
- Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph
- On the Complexity of the Planar Slope Number Problem
- A linear time algorithm for minimum link paths inside a simple polygon
- Who Needs Crossings? Hardness of Plane Graph Rigidity
- 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
- Drawing graphs on few lines and few planes
- Complexity of Geometric k-Planarity for Fixed k
- The Complexity of Simultaneous Geometric Graph Embedding
- ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
- How to Draw a Graph
- On the Complexity of Some Geometric Problems With Fixed Parameters
- Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
- Graph Drawing
- Drawing Partially Embedded and Simultaneously Planar Graphs
