Crossing minimization in linear embeddings of graphs

1990/01/01 by Shinya Masuda, K. Nakajima, Toshinobu Kashiwabara +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #VLSI and FPGA Design Techniques #Embedding #Combinatorics #Minification #Enhanced Data Rates for GSM Evolution #Computer science #Discrete mathematics #Mathematics #Line (geometry) #Mathematical optimization #Artificial intelligence #Geometry

paper · doi:10.1109/12.46286

openalex publication_date 1990/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The problem of embedding a graph in the plane with the minimum number of edge crossings arises in some circuit layout problems. It has been known to be NP-hard in general. Recently, in the area of book embedding, this problem was shown to be NP-hard even when the vertices are placed on a straight line l. The authors show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined.>

Citations

• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Permutation procedure for minimising the number of crossings in a network
• Efficient Planarity Testing
• The book thickness of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of Coloring Circular Arcs and Chords

Cited by

• Book embeddings and crossing numbers
• Book embedding [wikipedia]