Obstacle numbers of planar graphs

DOI10.1007/978-3-319-73915-1_6MaRDI QIDQ4625101zbMATH OpenOpenAlexFDO

Authors P. Ossona de Mendez, Pavel Valtr, John Gimbel

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given finitely many connected polygonal obstacles $O_1,dots,O_k$ in the plane and a set $P$ of points in general position and not in any obstacle, the {em visibility graph} of $P$ with obstacles $O_1,dots,O_k$ is the (geometric) graph with vertex set $P$, where two vertices are adjacent if the straight line segment joining them intersects no obstacle. The obstacle number of a graph $G$ is the smallest integer $k$ such that $G$ is the visibility graph of a set of points with $k$ obstacles. If $G$ is planar, we define the planar obstacle number of $G$ by further requiring that the visibility graph has no crossing edges (hence that it is a planar geometric drawing of $G$). In this paper, we prove that the maximum planar obstacle number of a planar graph of order $n$ is $n-3$, the maximum being attained (in particular) by maximal bipartite planar graphs. This displays a significant difference with the standard obstacle number, as we prove that the obstacle number of every bipartite planar graph (and more generally in the class PURE-2-DIR of intersection graphs of straight line segments in two directions) of order at least $3$ is $1$.

Recommendations

• On the structure of graphs with low obstacle number
• Graphs with large obstacle numbers
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Lower bounds on the obstacle number of graphs

Cites work

• Automatic search of truncated impossible differentials for word-oriented block ciphers
• Block ciphers -- focus on the linear layer (feat. PRIDE)
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials
• Cube Attacks on Tweakable Black Box Polynomials
• GIFT: a small present. Towards reaching the limit of lightweight encryption
• Graphs on surfaces
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Impossible differentials of SPN ciphers
• Improbable differential attacks on \texttt{PRESENT} using undisturbed bits
• Links among impossible differential, integral and zero correlation linear cryptanalysis
• New impossible differential search tool from design and cryptanalysis aspects. Revealing structural properties of several ciphers
• PRESENT: An Ultra-Lightweight Block Cipher
• Progress in Cryptology - INDOCRYPT 2003
• Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis
• The PHOTON family of lightweight hash functions
• Toward a theory of crossing numbers
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane

Cited in

(6)

• Geodesic obstacle representation of graphs
• Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
• Obstructing visibilities with one obstacle
• Geodesic obstacle representation of graphs
• Bounding and computing obstacle numbers of graphs
• Bounding and computing obstacle numbers of graphs

This page was built for publication: Obstacle numbers of planar graphs

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