Session B2 - Graph Theory and Combinatorics
July 15, 14:30 ~ 15:20 - Room B7
Geometric Representations of Graphs: Partial Extensions versus Simltaneous Embeddings
Charles University, Prague, Czech Republic - firstname.lastname@example.org
Extending partial solutions is often provably more difficult than constructing a solution from scratch. Somewhat surprisingly for geometric representations of graphs, this does not seem to be the case. In most of the cases when the computational complexity of the extension problem is known, the complexity is the same as of the plain recognition problem. Another closely related problem are simultaneous representations of graphs. Closely related, but not always known to be of the same computational complexity. We will survey the known results, compare them, and comment on open problems. The classes of graphs we will be interested in are interval graphs, circle graphs, comparability graphs, and also several graph drawing types.