Conference abstracts

Session B2 - Graph Theory and Combinatorics

July 15, 14:30 ~ 15:20 - Room B7

Geometric Representations of Graphs: Partial Extensions versus Simltaneous Embeddings

Jan Kratochvil

Charles University, Prague, Czech Republic   -   honza@kam.mff.cuni.cz

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.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.