On geometric graphs with no \(k\) pairwise parallel edges
type: Item
instance of: scholarly article
title: On geometric graphs with no \(k\) pairwise parallel edges
zbMATH Open document ID: 0908.05035
DOI: 10.1007/PL00009364
published in: Discrete \& Computational Geometry
publication date: 1999-03-18T00:00:00Z
review text: Two edges of a geometric graph are called parallel if they are the opposite sides of a convex quadrilateral. Main results: if a geometric graph with \(n\) vertices has no pair of parallel edges, then it has at most \(2n-2\) edges. This solves a conjecture of Kupitz. Also, for any fixed \(k\geq 3\), any geometric graph with \(n\) vertices and with no \(k\) pairwise parallel edges contains at most \(O(n)\) edges.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1164651
zbMATH Keywords: geometric graph
zbMATH Keywords: parallel edges
author: Pavel Valtr
reviewed by: Stelian Mihalas
MaRDI profile type: Publication
full work available at URL: pl00009364
OpenAlex ID: W1966860149
description: scientific article; zbMATH DE number 1164651