Asset Details
Do you wish to reserve the book?
Simple Realizability of Complete Abstract Topological Graphs Simplified
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Simple Realizability of Complete Abstract Topological Graphs Simplified
Do you wish to request the book?
Simple Realizability of Complete Abstract Topological Graphs Simplified
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
Simple Realizability of Complete Abstract Topological Graphs Simplified
2020
Overview
An abstract topological graph (briefly an AT-graph) is a pair A=(G,X) where G=(V,E) is a graph and X⊆E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exactly once and no other pair crosses. We show that simply realizable complete AT-graphs are characterized by a finite set of forbidden AT-subgraphs, each with at most six vertices. This implies a straightforward polynomial algorithm for testing simple realizability of complete AT-graphs, which simplifies a previous algorithm by the author. We also show an analogous result for independent Z2-realizability, where only the parity of the number of crossings for each pair of independent edges is specified.
Publisher
Springer Nature B.V
Subject
