Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
From MaRDI portal
Publication:3057631
DOI10.1007/978-3-642-16926-7_25zbMath1309.68146OpenAlexW1480586647MaRDI QIDQ3057631
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, David Ilcinkas
Publication date: 16 November 2010
Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_25
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ On plane geometric spanners: a survey and open problems ⋮ Spanning properties of Theta-Theta-6 ⋮ Theta-3 is connected ⋮ Dushnik-Miller dimension of TD-Delaunay complexes ⋮ Generalized sweeping line spanners ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition ⋮ Generalized sweeping line spanners ⋮ Cone-based spanners of constant degree ⋮ Strong matching of points with geometric shapes ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Towards tight bounds on theta-graphs: more is not always better ⋮ Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ On bounded degree plane strong geometric spanners ⋮ Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations ⋮ Construction and Local Routing for Angle-Monotone Graphs ⋮ The weighted barycenter drawing recognition problem ⋮ On plane constrained bounded-degree spanners ⋮ Morphing Schnyder drawings of planar triangulations ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ The \(\varTheta_5\)-graph is a spanner ⋮ Constrained routing between non-visible vertices ⋮ The Price of Order ⋮ The Price of Order ⋮ Hamiltonicity for convex shape Delaunay and Gabriel graphs ⋮ Fixed-orientation equilateral triangle matching of point sets ⋮ Asymptotics of geometrical navigation on a random set of points in the plane ⋮ Odd Yao-Yao Graphs are Not Spanners ⋮ Reprint of: Theta-3 is connected ⋮ Unnamed Item ⋮ A simple, faster method for kinetic proximity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On plane geometric spanners: a survey and open problems
- Delaunay graphs are almost as good as complete graphs
- Toughness and Delaunay triangulations
- On the geometric dilation of closed curves, graphs, and point sets
- Schnyder woods and orthogonal surfaces
- Planar graphs and poset dimension
- Classes of graphs which approximate the complete Euclidean graph
- Graph-theoretical conditions for inscribability and Delaunay realizability
- Planar graphs as minimal resolutions of trivariate monomial ideals
- There are planar graphs almost as good as the complete graph
- π/2-Angle Yao Graphs Are Spanners
- Geometric Spanner Networks
- Spanners of Additively Weighted Point Sets
- Plane Spanners of Maximum Degree Six
- On the Stretch Factor of Convex Delaunay Graphs
- Generalization of Voronoi Diagrams in the Plane
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
- Distributed Computing: A Locality-Sensitive Approach
- An Optimal Synchronizer for the Hypercube
