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.
Problemet med samtidig inbäddning av plana grafer infördes i REF, där det visas att par av banor, cykler och larver alltid kan realiseras, medan för allmänna plana grafer och även yttre plana grafer är detta inte alltid möjligt.
On Simultaneous Graph Embedding
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}