A space-filling complete graph.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1065.05035
publication date: 2005-07-20T00:00:00Z
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1600971
zbMATH Keywords: infinite graph
zbMATH Keywords: straight-line embedding
MaRDI profile type: Publication
author: J. Ginsburg
author: V. Linek
title: A space-filling complete graph.
published in: Ars Combinatoria
review text: A straight-line embedding of a graph \(G\) into \(\mathbb R^3\) is an injective mapping \(f\: V(G)\rightarrow \mathbb R^3\) such that the open segments \((f(u),f(v))\), \(\{u,v\} \in E(G)\), are pairwise disjoint and also disjoint from the images of all vertices. It is shown that any graph \(G\) with \(| V(G)| = \mathfrak c\) (continuum) and containing a matching of cardinality \(\mathfrak c\) has a space-filling straight-line embedding, i.e.\ one with \((\bigcup _{v\in V(G)} f(v))\cup (\bigcup _{\{u,v\}\in E(G)} (f(u),f(v))) = \mathbb R^3\). The proof proceeds by transfinite induction and uses the axiom of choice. It is also shown that a graph whose edges can be covered by finitely many vertices does not have a space-filling straight-line embedding into the plane. The analogous question for \(\mathbb R^3\) remains open.
reviewed by: Jiří Matoušek
description: scientific article; zbMATH DE number 1600971