On triconnected and cubic plane graphs on given point sets

DOI10.1016/j.comgeo.2009.03.005zbMath1200.05062OpenAlexW2083702278WikidataQ61732486 ScholiaQ61732486MaRDI QIDQ833718

Ferran Hurtado, Pavel Valtr, Clemens Huemer, Alfredo Daniel Garcia, F. Javier Tejel

Publication date: 14 August 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.03.005

zbMATH Keywords

cubic graphgeometric graphplane graph3-connected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Augmenting the edge connectivity of planar straight line graphs to three, Cubic plane graphs on a given point set, On Collinear Sets in Straight-Line Drawings, Geometric biplane graphs. II: Graph augmentation, Four-connected triangulations of planar point sets

Cites Work

• Augmenting the connectivity of geometric graphs
• Edge-connectivity augmentation problems
• Degree constrained tree embedding into points in the plane
• Straight-line embeddings of two rooted trees in the plane
• Successive edge-connectivity augmentation problems
• The rooted tree embedding problem into points in the plane
• Independence free graphs and vertex connectivity augmentation
• A smallest augmentation to 3-connect a graph
• On embedding an outer-planar graph in a point set
• Triangulating with high connectivity.
• Research Problems in Discrete Geometry
• Augmentation Problems
• Optimal Algorithms to Embed Trees in a Point Set
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Augmenting Outerplanar Graphs
• More on Finite Subsets and Simple Closed Polygonal Paths
• Embedding planar graphs at fixed vertex locations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item