Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Computer algorithms --- Congresses --- Computer Science --- Engineering & Applied Sciences --- Computer science. --- Computer communication systems. --- Data structures (Computer science). --- Computers. --- Algorithms. --- Computer science --- Probabilities. --- Computer Science. --- Theory of Computation. --- Algorithm Analysis and Problem Complexity. --- Discrete Mathematics in Computer Science. --- Computer Communication Networks. --- Data Structures. --- Probability Theory and Stochastic Processes. --- Mathematics. --- Information theory. --- Computer software. --- Computational complexity. --- Data structures (Computer scienc. --- Distribution (Probability theory. --- Distribution functions --- Frequency distribution --- Characteristic functions --- Probabilities --- Complexity, Computational --- Electronic data processing --- Machine theory --- Software, Computer --- Computer systems --- Communication theory --- Communication --- Cybernetics --- Computer science—Mathematics. --- Probability --- Statistical inference --- Combinations --- Mathematics --- Chance --- Least squares --- Mathematical statistics --- Risk --- Information structures (Computer science) --- Structures, Data (Computer science) --- Structures, Information (Computer science) --- File organization (Computer science) --- Abstract data types (Computer science) --- Communication systems, Computer --- Computer communication systems --- Data networks, Computer --- ECNs (Electronic communication networks) --- Electronic communication networks --- Networks, Computer --- Teleprocessing networks --- Data transmission systems --- Digital communications --- Electronic systems --- Information networks --- Telecommunication --- Cyberinfrastructure --- Network computers --- Algorism --- Algebra --- Arithmetic --- Automatic computers --- Automatic data processors --- Computer hardware --- Computing machines (Computers) --- Electronic brains --- Electronic calculating-machines --- Electronic computers --- Hardware, Computer --- Calculators --- Cyberspace --- Distributed processing --- Foundations --- Computer algorithms - Congresses

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

ThisvolumecontainsthepaperspresentedattheFourthInternationalConf- enceonFunwithAlgorithms(FUN2007),heldJune3-5,2007inthebeautiful TuscaniancoastaltownofCastiglioncello,Italy. FUN is a three-yearly conference dedicated to the use, design, and ana- sisofalgorithmsanddatastructures,focusingonresultsthatprovideamusing, witty but nonetheless originaland scienti?cally profound contributions to the area. ThepreviousthreemeetingswereheldonElbaIsland,Italy,andspecial issuesofthejournals Theoretical Computer Science (FUN1998), Discrete - plied Mathematics(FUN2001),andTheory of Computing Systems(FUN2004) featureextendedversionsofselectedpapersfromthethreeconferenceprograms. InresponsetotheCallforPapersforFUN2007,wereceived41submissions from 25 countries. Each submission was reviewed by at least three Program Committeemembers. Attheendoftheselectionprocess,thecommitteedecided toaccept20papers. TheprogramalsoincludesthreeinvitedtalksbyGiuseppe Di Battista (U. Rome III, Italy), Nicola Santoro (Carleton U. , Canada), and LucaTrevisan(U. C. Berkeley,USA). WewishtothankalltheauthorswhosubmittedtheirpaperstoFUN2007 andthuscontributedtothecreationofahigh-qualityprogramandentertaining meeting,aswellasthecolleagueswhoacceptedtoserveontheProgramC- mitteeandprovidedinvaluablehelpwiththereviewingprocess. Wealsowishto thanktheexternalreviewers(listedonthefollowingpages)includingthosewho completedurgentreviewsduringthediscussionphase. Papersubmission,sel- tion,andgenerationoftheproceedingswasgreatlyeasedbytheuseofthepubl- domainEasyChair ConferenceSystem(http://www. easychair. org). Wewish tothanktheEasyChaircreatorsandmaintainersfortheirsel?esscommittment tothescienti?ccommunity. Finally,specialthanksgotoVincenzoGervasi,whose constanthelpanddedicationwascrucialinmakingFUN2007asuccessfulevent. April2007 PierluigiCrescenzi GiuseppePrencipe GeppinoPucci Conference Organization Program Chairs PierluigiCrescenzi(UniversityofFirenze,Italy) GeppinoPucci(UniversityofPadua,Italy) Program Committee NancyAmato(TexasA&MUniversity,USA) NinaAmenta(UniversityofCaliforniaatDavis,USA) MarcellaAnselmo(UniversityofSalerno,Italy) AnnaBernasconi(UniversityofPisa,Italy) PaoloBoldi(UniversityofMilano,Italy) IreneFinocchi(UniversityofRoma LaSapienza ,Italy) LuisaGargano(UniversityofSalerno,Italy) SandyIrani(UniversityofCaliforniaatIrvine,USA) ChristosKaklamanis(UniversityofPatras,Greece) ShayKutten(Technion,Haifa,Israel) FabrizioLuccio(UniversityofPisa,Italy) BernardMans(MacquarieUniversity,Australia) PaoloPenna(UniversityofSalerno,Italy) AndreaRicha(ArizonaStateUniversity,Tempe,USA) IainStewart(UniversityofDurham,UK) ErkkiSutinen(UniversityofJoensuu,Finland) DenisTrystram(ID-IMAGGrenoble,France) PeterWidmayer(ETHZurich,Switzerland) Local Organization VincenzoGervasi(UniversityofPisa,Italy) GiuseppePrencipe(UniversityofPisa,Italy) External Reviewers LucaBecchetti HajoBroersma ValentinaCiriani DavidCoudert StefanDantchev AnnalisaDeBonis GianlucaDeMarco VIII Organization MiriamDiIanni PaolaFlocchini TomFriedetzky GiuliaGalbiati GoranKonjevod ZviLotker OrnellaMenchi FilippoMignosi ManalMohammed MelihOnus LindaPagli FannyPascual AndreaPietracaprina SrinivasaRao AdeleRescigno AndreaRicha GianlucaRossi MassimoSantini ErikSaule MarinellaSciortino RiccardoSilvestri CorinneTouati DenisTrystram SebastianoVigna IvanVisconti DonglinXia MicheleZito RosalbaZizza Table of Contents On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 GiuseppeDiBattista,FabrizioFrati,andMaurizioPatrignani Close Encounters With a Black Hole or Explorations and Gatherings in Dangerous Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 NicolaSantoro Fun with Sub-linear Time Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 LucaTrevisan Wooden Geometric Puzzles: Design and Hardness Proofs. . . . . . . . . . . . . . 16 HelmutAlt,HansBodlaender,MarcvanKreveld,Gu ¨nterRote,and GerardTel HIROIMONO Is NP-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 DanielAndersson Tablatures for Stringed Instruments and Generating Functions. . . . . . . . . 40 DavideBaccherini,DonatellaMerlini,andRenzoSprugnoli Knitting for Fun: A Recursive Sweater. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Complex analysis --- Discrete mathematics --- Computer science --- Artificial intelligence. Robotics. Simulation. Graphics --- discrete wiskunde --- complexe analyse (wiskunde) --- grafische vormgeving --- informatica --- database management --- programmatielogica --- KI (kunstmatige intelligentie)