Algorithms for graphs embeddable with few crossings per edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker [1] and Eppstein [3] to a much broader class of graphs.

MoreLess

Year of publication:	2004
Authors:	Bodlaender, Hans ; Grigoriev, Alexander
Institutions:	Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization
Subject:	operations research and management science

More details

Extent:	application/pdf
Series:	Research Memoranda.
Type of publication:	Book / Working Paper
Language:	English
Notes:	The text is part of a series Research Memoranda Number 036
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005670216