Geodesic
Graphs with Obstacle Number Greater than One
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1107-1119.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

An obstacle representation of a graph $G$ is a straight-line drawing of $G$ in the plane, together with a collection of connected subsets of the plane, called obstacles, that block all non-edges of $G$ while not blocking any edges of $G$. The obstacle number $\mathrm{obs}(G)$ is the least number of obstacles required to represent $G$. We study the structure of graphs with obstacle number greater than one. We show that the icosahedron has obstacle number $2$, thus answering a question of Alpert, Koch, Laison asking whether all planar graphs have obstacle number at most $1$. We also show that the $1$-skeleta of two related polyhedra, the gyroelongated $4$-bipyramid and the gyroelongated $6$-bipyramid, have obstacle number $2$. The order of the former graph is $10$, which is also the order of the smallest known graph with obstacle number $2$, making this the smallest known planar graph with obstacle number $2$. Our methods involve instances of the Satisfiability problem; we make use of various "SAT solvers" in order to produce computer-assisted proofs.
DOI : 10.7155/jgaa.00452
Keywords: graphs, graph drawing, obstacle number 
@article{JGAA_2017_21_6_a6,
     author = {Leah Wrenn Berman and Glenn Chappell and Jill Faudree and John Gimbel and Chris Hartman and Gordon Williams},
     title = {Graphs with {Obstacle} {Number} {Greater} than {One}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1107--1119},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2017},
     doi = {10.7155/jgaa.00452},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00452/}
}
TY  - JOUR
AU  - Leah Wrenn Berman
AU  - Glenn Chappell
AU  - Jill Faudree
AU  - John Gimbel
AU  - Chris Hartman
AU  - Gordon Williams
TI  - Graphs with Obstacle Number Greater than One
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 1107
EP  - 1119
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00452/
DO  - 10.7155/jgaa.00452
LA  - en
ID  - JGAA_2017_21_6_a6
ER  - 
%0 Journal Article
%A Leah Wrenn Berman
%A Glenn Chappell
%A Jill Faudree
%A John Gimbel
%A Chris Hartman
%A Gordon Williams
%T Graphs with Obstacle Number Greater than One
%J Journal of Graph Algorithms and Applications
%D 2017
%P 1107-1119
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00452/
%R 10.7155/jgaa.00452
%G en
%F JGAA_2017_21_6_a6
Leah Wrenn Berman; Glenn Chappell; Jill Faudree; John Gimbel; Chris Hartman; Gordon Williams. Graphs with Obstacle Number Greater than One. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1107-1119. doi : 10.7155/jgaa.00452. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00452/

Cité par Sources :