Template-type: ReDif-Paper 1.0
Author-Name: Bodlaender Hans 
Author-Name: Grigoriev Alexander
Author-workplace-name: METEOR
Title: Algorithms for graphs embeddable with few crossings per edge
Abstract: 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.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2004
Number: 036
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:dfa150f5-366c-4fed-a557-d7e7e7d3e75f/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 130097
Handle: RePEc:unm:umamet:2004036