Reduced constants for simple cycle graph separation
type: Item
instance of: scholarly article
title: Reduced constants for simple cycle graph separation
zbMATH Open document ID: 0865.05049
author: Hristo N. Djidjev
author: Shankar M. Venkatesan
published in: Acta Informatica
publication date: 1997-06-05T00:00:00Z
review text: If \(G\) is an \(n\) vertex maximal planar graph and \(\delta\leq 1/3\), then the vertex set of \(G\) can be partitioned into three sets \(A\), \(B\), \(C\) such that neither \(A\) nor \(B\) contains more than \((1- \delta)n\) vertices, no edge from \(G\) connects a vertex in \(A\) to a vertex in \(B\), and \(C\) is a cycle in \(G\) containing no more than \((\sqrt {2\delta}+ \sqrt {2-2\delta}) \sqrt {n}+ O(1)\) vertices. Specifically, when \(\delta= 1/3\), the separator \(C\) is of size \((\sqrt {2/3}+ \sqrt {4/3}) \sqrt {n}+ O(11)\), which is roughly \(1.97 \sqrt {n}\). The constant 1.97 is an improvement over the best known so far result of Miller \(2\sqrt {2} \approx 2.82\). If non-negative weights adding to at most 1 are associated with the vertices of \(G\), then the vertex set of \(G\) can be partitioned into three sets \(A\), \(B\), \(C\) such that neither \(A\) nor \(B\) has weight exceeding \(1- \delta\), no edge from \(G\) connects a vertex in \(A\) to a vertex in \(B\), and \(C\) is a simple cycle with no more then \(2\sqrt {n}+ O(1)\) vertices.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 918707
zbMATH Keywords: cycle graph separation
MaRDI profile type: Publication
full work available at URL: s002360050082
OpenAlex ID: W1996700055
DOI: 10.1007/S002360050082
description: scientific article; zbMATH DE number 918707