Abstrakt. Vi anser att problemet med samtidig inbäddning av planar grafer. Det finns två varianter av detta problem, en där kartläggningen mellan hörnen i de två graferna ges och en annan där kartläggningen inte ges. I synnerhet visar vi att utan kartläggning, något antal yttre plana grafer kan inbäddas samtidigt på ett O(n) × O(n) rutnät, och en yttre plana och allmänna plana graf kan inbäddas samtidigt på ett O(n 2 ) × O(n 3 ) rutnät. Om kartläggningen ges visar vi hur man bäddar in två vägar på ett n × n rutnät, eller två larvdiagram på ett O(n 2 ) × O(n 3 ) rutnät.
Mässing m.fl. REF beskriver linjära tidsalgoritmer för geometriska simultana inbäddningar av par av banor, cykler och larver, på ett O(n)×O(n) rutnät.
On Simultaneous Graph Embedding
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}