Hamiltonicity and Colorings of Arrangement Graphs
Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: felsner@inf.fu-berlin.de
Ferran Hurtado
Marc Noy
Dept. Matematica Aplicada 2
Universitat Politecnica de Catalunya
Pau Gargallo 5
Barcelona, Spain
email: name@ma2.upc.es.
Ileana Streinu
Dept. of Computer Science
Smith College
Northampton, MA 01063, USA
email: streinu@cs.smith.edu.
Report B-00-16
2000
We study connectivity, Hamilton path and Hamilton cycle decomposition,
4-edge and 3-vertex coloring for geometric graphs arising from
pseudoline (affine
or projective) and pseudocircle (spherical) arrangements.
While arrangements as geometric objects are well studied in discrete and
computational geometry, their graph theoretical properties seem to have
received little attention
so far. In this paper we show that they provide well structured
examples of families of planar and projective-planar graphs with very
interesting properties. Most prominently, spherical arrangements admit
decompositions into two Hamilton cycles and 4-edge colorings, but other
classes have interesting properties as well: 4-connectivity, 3-vertex
coloring or Hamilton paths and cycles. We show a number of negative results
as well: there are projective arrangements which cannot be 3-vertex
colored.
A number of conjectures and open questions accompany our
results.
Get the report here or by anonymous ftp:
Server: ftp.inf.fu-berlin.de
File: pub/reports/tr-b-00-16.ps.gz