Informace o publikaci
Drawing Bipartite Graphs in Two Layers with Specified Crossings
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek ve sborníku |
| Konference | 5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-030-11509-8_9 |
| Klíčová slova | Abstract topological graph; Bipartite graph; Permutation graph; Two-layer drawing |
| Popis | We give a polynomial-time algorithm to decide whether a bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of edges cross. This is a generalization of the problem of recognizing permutation graphs, and we generalize the characterization of permutation graphs. |
| Související projekty: |