Premium
On point‐halfspace graphs
Author(s) -
Scheinerman Edward R.,
Trenk Ann N.,
Ullman Daniel
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200103
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , point (geometry) , discrete mathematics , geometry
The following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point‐halfspace graph (in R k ) provided one can assign to each vertex v ϵ ( G ) a point p v R k and to each edge e ϵ E ( G ) a closed halfspace H e ϵ R k so that v is incident with e if and only if p v ϵ H e . Let H k denote the set of point‐halfspace graphs (in R k ). We give complete forbidden subgraph and structural characterizations of the classes H k for every k . Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc.