𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On point-halfspace graphs

✍ Scribed by Edward R. Scheinerman; Ann N. Trenk; Daniel Ullman

Book ID
102893239
Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
744 KB
Volume
20
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

On the critical point-arboricity graphs
On the critical point-arboricity graphs
✍ Riste Škrekovski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of __k__‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph __G__ embedded on a surface __S__ with Euler genus __

On point-linear arboricity of planar gra
On point-linear arboricity of planar graphs
✍ Jianfang Wang 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 220 KB

The point-linear arboricity of a graph G = (V, E), written as p,(G), is defined as p,(G) =min{k / there exists a partition of V into k subsets, V =LJt, V,, such that (V,) is a linear forest for 1 <i <k}. In this paper, we will discuss the point-linear arboricity of planar graphs and obtained follow

On 1-factors of point determining graphs
On 1-factors of point determining graphs
✍ Dennis P. Geoffroy 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 532 KB

A graph G is said to be point determinie, g if and only if distinct poiuts of G have distinc~ neigh~orhcods~ Fo: such a graph G. the nucleus is defined to !'.e the set G ~ consisting of a!! points v o[ G for ~vhich G-r is a point determini~'g graph. h~ [4]. Samner exhibited several famiiies of grat

On point-sets that support planar graphs
On point-sets that support planar graphs
✍ V. Dujmović; W. Evans; S. Lazard; W. Lenhart; G. Liotta; D. Rappaport; S. Wismat 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 612 KB