On hardness of the joint crossing number Conference Paper

•  
• Overview
•  
• Research
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

abstract

• The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for smallgenus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar. © Springer-Verlag Berlin Heidelberg 2015.

authors

• Hliněný P.
• Salazar Anaya Gelasio

publication date

• 2015-01-01

funding provided via

• Consejo Nacional de Ciencia y Tecnología, CONACYT: 222667  Grant
• Grantová Agentura České Republiky, GA ČR: P202/12/G061  Grant

published in

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  Journal

Research

keywords

• Computers; Crossing number; Diagonal flip; Edge crossing; NP-hard; Orientable surfaces; Two-graphs; Artificial intelligence

Identity

Digital Object Identifier (DOI)

• 10.1007/978-3-662-48971-051

Additional Document Info

start page

• 603

end page

• 613

volume

• 9472