Contents

Ars Combinatoria

  • Research article

A Note on the Spatiality Degree of Graphs

Pierluigi Crescenzi1, Sergio De Agostino2, Riccardo Silvestri3
1Dipartimento di Sistemi ed Informatica, Universita di Firenze 50134 Firenze, Italy
2Computer Science Department Armstrong Atlantic State University Savannah, Georgia 31419-1997, USA
3Dipartimento di Matematica Pura ed Applicata Universita de L’Aquila 67100 L’ Aquila, Italy
  • Published: 30/04/2002

Abstract

We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.

Citation
Pierluigi Crescenzi, Sergio De Agostino, Riccardo Silvestri. A Note on the Spatiality Degree of Graphs[J], Ars Combinatoria, Volume 063. 185-191. .