Abstrakt. Två grafer G1 = (V, E1) och G2 = (V, E2) medger en geometrisk samtidig inbäddning om det finns en uppsättning punkter P och en bijection M : P → V som inducerar plana raka inbäddningar både för G1 och för G2. Även om det är känt att två larver alltid medger en geometrisk samtidig inbäddning och att två träd inte alltid medger ett, är frågan om ett träd och en stig fortfarande öppen och betraktas ofta som det mest framträdande öppna problemet i detta område. Vi besvarar denna fråga negativt genom att ge ett motexempel. Dessutom, eftersom motexempelet använder separata kantuppsättningar för de två graferna, svarar vi också negativt på en annan öppen fråga, det vill säga om det är möjligt att samtidigt bädda in två kantavskiljande träd. Som ett slutresultat studerar vi samma problem när vissa begränsningar på trädet införs. Nämligen visar vi att ett träd på djup 2 och en stig alltid medger en geometrisk samtidig inbäddning. I själva verket är en sådan stark begränsning inte så långt från att överbrygga klyftan med de fall som inte medger någon lösning, eftersom trädet som används i vårt motexempel har djup 4.
Angelini m.fl. REF visade samma resultat för en stig och ett träd.
On a Tree and a Path with no Geometric Simultaneous Embedding
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}