Drawing Bipartite Graphs in Two Layers with Specified Crossings
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Proceedings |
| Conference | 5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019) |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-3-030-11509-8_9 |
| Keywords | Abstract topological graph; Bipartite graph; Permutation graph; Two-layer drawing |
| Description | 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. |
| Related projects: |