Geometric biplane graphs. II: Graph augmentation

DOI10.1007/S00373-015-1547-0MaRDI QIDQ2345512zbMATH OpenOpenAlexFDO

Authors Matias Korman, Inês Matos, Maria Saumell, Rodrigo I. Silveira, Csaba D. Tóth, Alfredo García, Ferran Hurtado, Javier Tejel

Publication date 22 May 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-connected graphsbiplane graphsgeometric graphsgraph augmentation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Abstract: We study biplane graphs drawn on a finite point set $S$ in the plane in general position. This is the family of geometric graphs whose vertex set is $S$ and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges.

Recommendations

• Geometric biplane graphs. I: Maximal graphs
• Connectivity augmentation in plane straight line graphs
• Augmenting the connectivity of geometric graphs
• Connectivity augmentation in planar straight line graphs
• Augmenting the connectivity of planar and geometric graphs

Cites work

• A Generation Procedure for the Simple 3-Polytopes With Cyclically 5-Connected Graphs
• A Theorem on Planar Graphs
• Applications of a semi-dynamic convex hull algorithm
• Approximating the edge length of 2-edge connected planar geometric graphs on a set of points
• Augmentation Problems
• Augmenting the connectivity of geometric graphs
• Augmenting the connectivity of planar and geometric graphs
• Augmenting the edge connectivity of planar straight line graphs to three
• Bounded length, 2-edge augmentation of geometric planar graphs
• Connectivity augmentation in planar straight line graphs
• Constrained tri-connected planar straight line graphs
• Construction of planar triangulations with minimum degree 5
• Fast Algorithms for Finding Nearest Common Ancestors
• Four-connected triangulations of planar point sets
• Geometric biplane graphs. I: Maximal graphs
• Geometric biplane graphs. II: Graph augmentation
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On generating planar graphs
• On representations of some thickness-two graphs
• On triconnected and cubic plane graphs on given point sets
• Plane geometric graph augmentation: a generic perspective
• The book thickness of a graph
• Triangulating with high connectivity.

Cited in

(6)

• Geometric biplane graphs. I: Maximal graphs
• Geometric biplane graphs. II: Graph augmentation
• Plane augmentation of plane graphs to meet parity constraints
• The Mathematics of Ferran Hurtado: A Brief Survey
• Augmenting plane straight-line graphs to meet parity constraints
• Linear-size planar Manhattan network for convex point sets

This page was built for publication: Geometric biplane graphs. II: Graph augmentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345512)