Det geometriska simultana inbäddningsproblemet ställer frågan om två plana grafer på samma uppsättning hörn i planet kan ritas med hjälp av raka linjer, så att varje graf är plan. Geometriska samtidiga inbäddning är ett aktuellt ämne i grafritning och positiva och negativa resultat är kända för olika klasser av grafer. Hittills har endast anslutna grafer beaktats. I detta papper presenterar vi de första resultaten för inställningen där en av graferna är en matchning. I synnerhet visar vi att det finns en planar graf och en matchning som inte medger en geometrisk samtidig inbäddning. Detta stärker ett analogt negativt resultat för en planar graf och en väg. På den positiva sidan beskriver vi algoritmer som beräknar en geometrisk samtidig inbäddning av ett matchande och ett hjul, en yttre stig eller ett träd. Våra ritningsalgoritmer minimerar antalet orienteringar som används för att rita kanterna på matchningen. Särskilt när vi inbäddar ett matchande och ett träd, kan vi rita alla matchande kanter horisontellt. När vi lägger in en matchande och ett hjul eller en yttre väg, använder vi bara två riktningar.
Cabello m.fl. REF visade att en geometrisk samtidig ritning av ett matchande och a) ett hjul, b) en yttre stig eller c) ett träd alltid existerar.
Geometric Simultaneous Embeddings of a Graph and a Matching
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}