52 citations · 118 across the 27 of their papers we have counts for
4 papers · 1 filter
Stackelberg Shortest Path Tree Game, Revisited
Sergio Cabello
Let be a directed graph with vertices and edges. The edges of are divided into two types: and . Each edge of has a fixed price. The edges…
Hardness of approximation for crossing number
Sergio Cabello
We show that, if P\not=NP, there is a constant c > 1 such that there is no c-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.
Adding one edge to planar graphs makes crossing number and 1-planarity hard
Sergio Cabello, Bojan Mohar
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar gra…
Multiple-Source Shortest Paths in Embedded Graphs
Sergio Cabello, Erin Wolf Chambers, Jeff Erickson
Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a rando…