Planar graphs with vertices in prescribed regions: models, algorithms, and complexity

Abstract

Il volume e la complessità delle informazioni relazionali strutturate, generate e gestite da odierni sistemi informatici è aumentato drasticamente. Sempre più spesso i dati vengono prodotti così rapidamente da non poter neppure essere visualizzati o immagazzinati interamente e l’analisi manuale del loro contenuto relazionale è spesso impraticabile. In uno scenario così complesso la creazione di nuovi paradigmi e la progettazione di algoritmi efficienti per il layout, l’esplorazione e l’analisi di grafi dinamici e di grandi dimensioni sono emersi come strategiche direzioni di ricerca, accompagnate sia da notevole interesse pratico che da un intrinseco fascino teorico. La classica nozione di grafo, come astrazione matematica usata per descrivere una relazione binaria tra un insieme di entità, è stata estesa per rispondere a queste nuove esigenze. Nuovi e potenziati modelli di grafi sono stati concepiti in grado di rappresentare aggregazioni, affinità semantiche, gerarchie, e relazioni multiple e/o dinamiche sullo stesso insieme di entità. Non è sorprendente, da un punto di vista cognitivo, che il modo più naturale e probabilmente più efficace per beneficiare dell’impiego di queste strutture combinatorie sia la loro visualizzazione. Infatti, il disegno di un grafo permette di coglierne rapidamente il contenuto relazionale. Tuttavia, non tutti i disegni sono ugualmente efficaci per trasmettere la struttura di un grafo. Il Graph Drawing è il settore di ricerca che si occupa della progettazione di algoritmi per produrre automaticamente rappresentazioni visive di grafi. Tra le caratteristiche di un “buon” disegno di un grafo, la planarità è senza alcun dubbio la più desiderata. Infatti, disegni di grafi senza incroci tra i gli archi sono più leggibili e più facili da navigare. Pertanto, al fine di produrre visualizzazioni piacevoli ed efficaci dei nuovi modelli di grafi, la direzione più promettente risulta essere quella di estendere il concetto standard di planarità anche a questi ultimi. In particolare i due nuovi modelli di grafi che hanno dominato la scena negli ultimi anni sono i clustered graphs (grafi clusterizzati) e i simultaneous graphs (grafi simultanei). Un grafo clusterizzato consiste in un grafo e in un raggruppamento gerarchico ricorsivo dei suoi vertici (clustering). I cluster possono essere utilizzati per rappresentare affinità semantiche tra vertici, astrarre sotto-strutture complesse mediante sotto-strutture semplici, e più in generale per arricchire un grafo con informazioni gerarchiche. Un grafo simultaneo può essere visto come un insieme di grafi che condividono gli stessi vertici o, in alternativa, come un unico grafo con diversi insiemi di archi. I grafi simultanei permettono di codificare relazioni differenti tra le stesse entità o l’evoluzione di una singola relazione nel tempo. Per questi modelli sono stati ideati diversi paradigmi di visualizzazione incentrati sul vincolare i vertici in regioni prescritte del piano. Ad esempio, i cluster sono generalmente rappresentati racchiudendo i vertici in regioni semplici chiuse, mentre la coerenza tra disegni dei diversi grafi costituenti un grafo simultaneo è ottenuta posizionando i loro vertici sullo stesso insieme di punti. In questa tesi sono presi in considerazione entrambi i modelli di grafi, clusterizzati e simultanei, e vengono studiate in particolare le due più famose nozioni di planarità per questi modelli, rispettivamente CLUSTERED PLANARITY (C-PLANARITY in breve) e Simultaneous Embedding with Fixed Edges (SEFE in breve). Inoltre, il presente lavoro estende il suo campo di indagine contemplando come possibili domini di embedding per i vertici non solo regioni semplici nidificate del piano e insiemi finiti di punti, ma anche singole linee, serie di linee parallele, e fasce illimitate e disgiunte del piano. Ad esempio, per quanto concerne i grafi simultanei, si sono studiati i problemi PARTITIONED k-PAGE BOOK EMBEDDING in cui i vertici sono vincolati a giacere su una linea, T -COHERENT LEVEL PLANARITY in cui i vertici sono vincolati a giacere su linee parallele, e STREAMED PLANARITY in cui i vertici sono confinati su un insieme finito di punti; nel contesto dei grafi clusterizzati, si sono studiati i problemi STRIP PLANARITY in cui i vertici sono assegnati a regioni orizzontalmente illimitate del piano tra loro disgiunte ed inoltre, richiedendo che i vertici giacciano su linee parallele e allo stesso tempo all'interno di regioni semplici nidificate che intersecano tali linee, si è studiato il problema CLUSTERED-LEVEL PLANARITY. I grafi clusterizzati sono stati introdotti congiuntamente alla nozione di C-PLANARITY, nella quale una rappresentazione sul piano di un grafo clusterizzato è ricercata in modo tale che il disegno sia planare e i cluster siano rappresentati da regioni semplici che racchiudono tutti e soli i vertici del cluster corrispondente, cosicché - per semplificare - non vi siano incroci “inutili” tra cluster ed archi. Questa nozione di planarità mira a mostrare contemporaneamente sia il contenuto informativo relazionale che quello gerarchico del grafo clusterizzato. Per grafi simultanei, invece, sono state introdotte molteplici nozioni di planarità. Tuttavia, grazie alle sue applicazioni pratiche e teoriche, quella di SEFE si è imposta senza alcun dubbio come la più rilevante. In un SEFE un grafo simultaneo deve essere disegnato nel piano in modo tale da indurre disegni planari di ciascuno dei suoi grafi costituenti e che archi multipli siano rappresentati da archi singoli. In alternativa, quando si considera ciascuno dei grafi costituenti separatamente, un SEFE può essere definito come un insieme di disegni planari, uno per ciascuno di questi grafi, definiti sullo stesso insieme di punti, in cui gli archi comuni a più grafi sono rappresentati dalle medesime curve. Questa variante di planarità mira a visualizzare chiaramente ciascuna delle relazioni che compongono un grafo simultaneo e, allo stesso tempo, al mantenimento della mappa mentale dell’utente durante l’esplorazione della struttura del grafo. Nonostante i notevoli sforzi investigativi spesi dalla comunità del Graph Drawing, determinare la complessità computazionale di questi problemi rimane una delle più stimolanti ed affascinanti domande aperte in questo settore di ricerca. Questa tesi contribuisce ad ampliare la comprensione delle relazioni tra le diverse e fondamentali varianti di planarità e ad espandere la conoscenza della complessità computazionale di alcune di queste varianti. In particolare si sono presi in considerazione grafi planari (Parte I), clustered graphs (Parte II), strip graphs e level graphs (Parte III), simultaneous graphs (Parte IV) e, infine, streamed graphs (Parte V). In questo lavoro trovano risposta i quesiti riguardanti la complessità computazionale di varianti notevoli del problema della planarità classica sulle quali era già stato avviato un notevole sforzo di ricerca nel corso degli ultimi due decenni. Inoltre, si è potuto arricchire con nuovi attori il palcoscenico della planarità, grazie all'introduzione e allo studio di nuove nozioni di planarità vincolata. Infine, sono stati portati alla luce importanti aspetti combinatori ed ideati algoritmi efficienti basati su di essi per testare alcuni di questi – vecchi o nuovi – problemi di planarità. La Figura 1 offre una panoramica di alcuni dei risultati presentati in questa tesi, dove l’enfasi è posta sulla relazione di riducibilità tra le diverse nozioni di planarità. Molti dei contributi algoritmici non sono tuttavia rappresentati in questo schema che pertanto è da considerarsi solo come una mappa aggiornata mirata ad aiutare il lettore nell’esplorazione del regno delle molteplici declinazioni della Planarità. La tesi è organizzata come segue. Oggetto della Parte I sono i grafi planari, i metodi più comunemente impiegati per rappresentare e gestire embedding planari, e le nozioni di planarità che sono il soggetto principale di questa tesi. Nel capitolo 1 vengono presentati definizioni e concetti preliminari concernenti i grafi planari ed i loro embedding e disegni planari. Nel capitolo 2 vengono discussi i concetti di base relativi alla connettività di grafi e sono illustrate le principali tecniche impiegate per descrivere e gestire gli embedding dei grafi planari in funzione del loro grado di connettività. In particolare, si illustra la struttura di dati SPQR-tree che permette di gestire in modo efficiente la decomposizione di un grafo biconnesso nelle sue componenti triconnesse. Nel capitolo 3 sono introdotti formalmente i problemi C-PLANARITY e SEFE. Inoltre, viene presentato lo stato dell’arte relativo agli algoritmi polinomiali noti per testare classi ristrette di istanze di questi problemi. La Parte II si incentra sui disegni dei grafi clusterizzati e sugli embedding vincolati di multi-grafi planari. Nel capitolo 4, al fine di far ulteriore luce sul problema di C-PLANARITY, si prende in considerazione una versione rilassata di questo problema in cui alcuni tipi di incroci (arco-arco, arco-cluster e cluster-cluster) sono ammessi, anche se il grafo sottostante è planare. Con questa impostazione il nostro principale risultato è un algoritmo polinomiale che verifica l’esistenza di un disegno con soli incroci di tipo clustercluster per grafi clusterizzati biconnessi. Questo risultato costituisce il primo esempio di condizione necessaria non triviale per C-PLANARITY che può essere testata in tempo polinomiale per una classe notevole di grafi clusterizzati. Nel capitolo 5, motivati dal fatto che molti problemi computazionalmente difficili e anche alcuni di complessità ancora ignota come il problema di C-PLANARITY sono noti essere decidibili in tempo polinomiale ad embedding fisso per grafi planari con facce di piccola dimensione, si sono studiati i problemi MINMAXFACE e UNIFORMFACES. Questi problemi richiedono di determinare embedding planari di multi-grafibiconnessi che, rispettivamente, minimizzino la dimensione della faccia più grande o in cui tutte le facce abbiano la medesima dimensione. Sebbene entrambi i problemi siano stati dimostrati computazionalmente difficili, si sono ideati algoritmi efficienti per varie interessanti classi di istanze per entrambi i problemi ed un algoritmo con fattore di approssimazione costante per il problema MINMAXFACE.La Parte III si occupa dei disegni di grafi clusterizzati in cui è richiesto che i vertici giacciano in regioni del piano orizzontalmente illimitate e tra loro disgiunte o su linee parallele. Nel capitolo 6 si è introdotto e studiato un nuovo concetto di planarità, chiamato STRIP PLANARITY, per grafi i cui vertici sono confinati in strisce (strips) del piano orizzontalmente illimitate e tra loro disgiunte, denominati strip graphs. Il problema ha forti relazioni con alcune delle più studiate varianti del problema della planarità,quali ad esempio C-PLANARITY, UPWARD PLANARITY e LEVEL PLANARITY. Infatti, si è potuta mostrare una riduzione polinomiale da questo problema al problema di C-PLANARITY, che ha quindi permesso di mettere in relazione la complessità computazionale di questi due problemi. Inoltre, viene presentato un algoritmo polinomiale per il test di STRIP PLANARITY ad embedding fisso, basato su molteplici tecniche di modifica dell’istanza originaria che permettono, in ultimo, di trasformare l’istanza di partenza in un insieme di istanze del problema di UPWARD PLANARITY ad embedding fisso. Nel capitolo 7 è oggetto di studio la complessità computazionale di due note nozioni di planarità relative al disegno di level graphs, ovvero i problemi di T -LEVEL PLANARITY e CLUSTERED-LEVEL PLANARITY. Un level graph è un grafo i cui vertici sono collocati su livelli o linee parallele ed i cui archi collegano solo vertici su livelli differenti. Il primo problema prende in considerazione level graphs arricchiti, esattamente come un grafo clusterizzato, con una clusterizzazione ricorsiva del loro insieme di vertici. Il secondo problema, invece, prende in considerazione level graphs in cui ad ogni livello è associato un albero che impone vincoli sui possibili ordinamenti dei vertici del livello corrispondente. A differenza di quanto avviene per la nozione classica di LEVEL PLANARITY si è potuto dimostrare che gli ulteriori vincoli introdotti sono sufficientia rendere questi problemi di planarità entrambi NP-completi, mentre essi sono risolvibili in tempo polinomiale quando ci limitiamo a level graphs i cui archi si estendono solo tra livelli consecutivi. Vale la pena sottolineare che quest’ultimo contributo algoritmico è stato ottenuto sfruttando una riduzione non triviale tra i due problemi e la loro stretta connessione con il problema SEFE. Osserviamo infine che l’NP-hardness di CLUSTERED-LEVEL PLANARITY presentata in questo capitolo costituisce, al meglio delle nostre conoscenze, il primo risultato di hardness per una variante del problema di C-PLANARITY nella quale nessuno dei vincoli propri di C-PLANARITY sia stato rimosso. Nella Parte IV viene approfondita l’indagine sul problema SEFE, concentrandosi in particolare sul caso in cui lo spazio di embedding dell’insieme dei vertici del grafo simultaneo sia una singola linea, e sul rapporto tra i problemi SEFE e C-PLANARITY. Il capitolo 8 è dedicato allo studio della complessità di alcuni problemi combinatori legati a SEFE. In particolare, vengono considerate le varianti del problema chiamate SUNFLOWER SEFE e PARTITIONED T-COHERENT k-PAGE BOOK EMBEDDING (PTBE-k in breve), note essere computazionalmente equivalenti sotto alcune condizioni. Vengono dimostrati alcuni risultati di hardness per questi problemi, anche per grafi simultanei composti da soli tre grafi planari e sotto forti restrizioni sul grado di connettività di tali grafi. In particolare i nostri risultati sul problema PTBE-k per istanze composte da un numero costante di grafi che condividono tutti il medesimo sottografo stella, caso citato come un problema aperto da Schaefer [Sch13] e Hoske [Hos12], complementano il lavoro di Hong e Nagamochi [HN14] su questo problema. In positivo, si è inoltre sviluppato un algoritmo lineare per PTBE-k per una interessante classe di grafi simultanei composti da un numero arbitrario di grafi planari. L’attenzione è poi rivolta al caso ancora aperto di SEFE in cui si considerano grafi simultanei composti da soli due grafi di input, chiamato SEFE-2. In primo luogo, si è dimostrato che nella versione “connessa” di questo problema, denominata C-SEFE-2, è possibile concentrare la nostra attenzione solo sul caso in cui uno dei due grafi ha una struttura particolare ed alta connettività. In secondo luogo, si è studiata la versione di ottimizzazione di questo problema in cui è richiesto di massimizzare il numero di archi comuni ai grafi di input disegnati nello stesso modo, chiamato MAX SEFE, che viene citato come un problema aperto da Haeupler et al. [HJL13] e nel Handbook of Graph Drawing and Visualization [BKR13], nel capitolo 11 (Problema aperto 9). Sono presentati risultati di NP-completezza del problema per molteplici istanze vincolate. Il capitolo 9 mira ad ampliare la comprensione delle relazioni tra i due principali problemi aperti nel Graph Drawing che sono gli oggetti principali di questa tesi, cioè i problemi SEFE e C-PLANARITY. L’equivalenza polinomiale tra questi due problemi costituisce infatti un intrigante quesito irrisolto. Una pietra miliare in questo contesto è stata offerta da Schaefer [Sch13], che ha per primo mostrato una riduzione da CPLANARITY a SEFE-2. Nella nostra ricerca si è potuto muovere un ulteriore passo in avanti nella comprensione del rapporto tra questi problemi, provando l’esistenza di una riduzione anche nella direzione opposta se consideriamo istanze di SEFE-2 in cui il grafo indotto dagli archi comuni è connesso (C-SEFE-2). La Parte V tratta il disegno di grafi non planari in cui un sottografo planare è privo di incroci e disegni di grafi che vengono rappresentati in modo streaming. Nel capitolo 10 si è avviato lo studio di un nuovo problema correlato a SEFE e, in particolare, al problema SUNFLOWER SEFE. Il focus di questa ricerca è sulla produzione di disegni di grafi non planari in cui un sottografo ricoprente planare è rappresentato senza incroci. In molti contesti applicativi gli archi di un grafo sono usati per esprimere connessioni tra entità di diversa importanza e significato. In questo caso l’interfaccia visuale può tentare di visualizzare gli archi più importanti senza intersezioni, trascurando le intersezioni che coinvolgono solo gli archi meno importanti. Inoltre, disegni in cui gli archi sono rappresentati come segmenti rettilinei, invece che come poli-linee, sono generalmente considerati più leggibili. Quindi, sembra sensato prendere in considerazione anche disegni in cui gli archi meno importanti abbiano piegamenti, richiedendo tuttavia che gli archi importanti siano rappresentati come segmenti rettilinei. Saranno presentati algoritmi per produrre questo tipo di disegni per varie classi di istanze, sia nello scena rio pienamente rettilineo che in quello in cui si ammette la presenza di poli-linee. Nel primo scenario sono discussi risultati positivi e negativi per diversi tipi di sotto-grafi ricoprenti connessi ed è presentato un algoritmo efficiente per il test di istanze in cui il sotto-grafo ricoprente che deve essere disegnato senza incroci è triconnesso. Nel secondo scenario sono invece presi in considerazione disegni con diversi compromessi tra il numero di piegamenti ammessi e l’area richiesta dal disegno; inoltre, si descrive un algoritmo di test per istanze il cui sotto-grafo ricoprente privo di incroci è biconnesso e gli archi possono avere al più un piegamento. Nel capitolo 11 viene infine introdotto e studiato un nuovo modello di grafi, chiamati streamed graphs, i cui archi sono presentati come un flusso in continua evoluzione nel tempo. Sono presi in considerazione streamed graphs composti da archi che appaiono in un determinato istante e sono visibili per una finestra temporale limitata prima di scomparire. Data una dimensione della finestra ! è stato definito il concetto di !-STREAM PLANARITY in cui occorre determinare disegni degli archi dello streamed graph che inducano disegni planari dello streamed graph in ogni istante temporale. Non è difficile convincersi del fatto che questa nozione di planarità possa essere interpretata come una variante di SEFE. Verrà dimostrata l’NP-completezza di questo problema anche quando la dimensione della finestra considerata è una costante. Inoltre, si prenderà in considerazione la variante del problema in cui un dato sotto-grafo dello streamed graph, chiamato backbone, sia imperituro, ovvero non scompaia mai dalla scena. In questo contesto è stato possibile mostrare l’NP-completezza del problema anche per ! = 2. In positivo, il capitolo offre la descrizione di un algoritmo lineare per quest’ultimo problema nel caso in cui ! = 1, condizione sotto la quale un algoritmo polinomiale era già stato presentato nel contesto della PARTIAL PLANARITY [Sch14] (il cui studio era stato motivato proprio dalla ricerca presentata nel capitolo 10). I nostri risultati implicano inoltre l’inesistenza, a meno che non sia verificata l’uguaglianza P=NP, di algoritmi FPT per SEFE e per il fondamentale problema di WEAK REALIZABILITY rispetto ad alcuni parametri notevoli.