On the Pseudolinear Crossing Number
Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph. © 2016 Wiley Periodicals, Inc.
publication date
published in
Research
keywords
-
crossing number; pseudoline arrangements; pseudolinear crossing number; rectilinear crossing number Graph theory; Crossing number; Graph G; Pseudo-line arrangements; Rectilinear crossing numbers; Geometry
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue