Abstrakt. Funktionsgrafer är grafer som kan representeras av skärningspunkter mellan kontinuerliga, realvärderade funktioner i intervallet [0, 1] och är kända för att vara exakt komplement till jämförelsegrafer. Som sådana är de igenkännliga i polynom tid. Funktionsgrafer generalisera permutationsgrafer, som uppstår när alla funktioner som anses vara linjära. Vi fokuserar på problemet med att utvidga partiella representationer, vilket generaliserar problemet med erkännande. Vi observerar att för permutationsgrafer kan en enkel förlängning av Golumbics jämförelsegrafigenkänningsalgoritm utnyttjas. Detta tillvägagångssätt misslyckas för funktionsdiagram. Icke desto mindre presenterar vi en polynom-tidsalgoritm för att förlänga en partiell representation av en graf genom funktioner som definieras i hela intervallet [0, 1] som tillhandahålls för några av hörnen. Å andra sidan visar vi att om en partiell representation består av funktioner som definieras på subintervaler av [0, 1], sedan problemet med att utöka denna representation till funktioner på hela intervallet [0, 1] blir NP-komplett.
Vi noterar att denna variation kan anges som problemet med att utvidga en partiell orientering av en permutationskurva till en 2-dimensionell partiell ordning REF.
Extending partial representations of function graphs and permutation graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}