Abstrakt. Squaregraphs definierades ursprungligen som finita plan grafer där alla inre ansikten är fyrsidiga (dvs 4-cycles) och alla inre hörn (dvs, hörnen inte incident med det yttre ansiktet) har grader större än tre. Den planar dual av en ändlig fyrkantig bestäms av en triangel-fri ackord diagram av enheten disk, som kunde alternativt ses som en triangel-fri linje arrangemang i det hyperboliska planet. Denna representation bär över till oändliga plan grafer med ändliga vertex grader där bollarna är ändliga squaregraphs. Algebraiskt, finita kvadratgrafer är mediangrafer för vilka dualerna är finita cirkulära splitsystem. Därför är squaregraphs på korspunkten av två dualiteter, en algebraic och en geometrisk en, och sålunda låna sig till flera kombinatoriska tolkningar och strukturella karakteriseringar. Med dessa och 5-färgbarhet teorem för cirkelgrafer till hands, visar vi att varje kvadratgraf kan isometriskt inbäddas i Cartesian produkten av fem träd. Detta inbäddande resultat kan också utvidgas till det oändliga fallet utan hänvisning till en inbäddning i planet och utan någon kardinalitet begränsning när formulerade för median grafer fria från kuber och ytterligare ändliga hinder. Vidare uppvisar vi en klass av kvadrater som kan inbäddas i produkten av tre träd och vi karakteriserar de kvadrater som är inbäddade i produkten av bara två träd. Slutligen har finita kvadratgrafer ett antal algoritmiska funktioner som inte sträcker sig till godtyckliga mediandiagram. Till exempel visar vi att median-genererande uppsättningar av finita kvadratografier kan beräknas i polynom tid, medan, inte oväntat, motsvarande problem för median grafer visar sig vara NP-hård. En finit kvadrat är en finit plan graf G = (V, E) (dvs. en finit graf ritad i planet utan kanter korsning) där alla inre ansikten är fyrsidiga och där alla arXiv:0905.4537v1 [math.CO]
Varje kvadrat är en partiell kub, och kvadrater kan kännas igen i linjär tid REF.
Combinatorics and geometry of finite and infinite squaregraphs
{'venue': 'SIAM J. Discrete Math. 24(4): 1399-1440, 2010', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}