תורת הגרפים היא הבסיס לדרך החשיבה של החוקרים והמהנדסים על רשתות כדוגמת רשתות תקשורת. מטרת המחקר היא לאפשר תיוג צמתים בגרפים המייצגים רשתות תקשורת עם שמות בעלי משמעות, כך שמשמות הצומת ניתן יהיה לרכוש מידע על מצב הרשת. למשל, בהינתן התיוג של שני צמתים ברשת נוכל לחשב את המרחק ברשת בין הצמתים רק על בסיס שמות הצמתים. מקרה פשוט לדוגמה הוא רשת שהיא עץ, כלומר גרף קשיר (קיים מסלול בין כל זוג צמתים) ללא מעגלים. אם משמות שני צמתים נוכל להסיק מיהו האב הקדמון המשותף שלהם, כי אז נוכל לחשב משמותיהם גם את המרחק ביניהם. במסגרת מחקרנו פיתחנו שיטות שונות לתיוג צמתים ואף הרחבנו מחקר זה למבנים נוספים. כמו כן פיתחנו פרוטוקולים לניתוב בין צמתים גם במקרה של תקלות ברשת, תוך שימוש במידע מועט בלבד ושימור מסלולים טובים לניתוב. את תוצאות המחקר פרסמנו בכנסים מובילים בתחום של מדעי המחשב וכן בכתבי עת מובילים בתחום. כפועל יוצא של המחקר פותחו גם אלגוריתמים יעילים למספר בעיות קשורות. אחת מהן היא חישוב הקוטר של גרף מישורי, כלומר המרחק המקסימלי בין שני צמתים בגרף. בעיה אחרת היא שידוך בין צמתים בגרף ("שידוך" בתורת הגרפים פירושו שלכל צומת יש בן זוג אחד ויחיד). בעיה נוספת שנחקרה היא מציאת מחרוזות קרובות זו לזו (מחרוזות יכולות להיות תיוגים של צמתים). במסגרת בעיה זו, מחפשים מחרוזת שבהינתן קבוצת מחרוזות היא לא רחוקה מאף אחת מהן יותר מדי – וזאת לפי מספר מדדים של מרחק. בעיה זו, שנקראת בעיית המחרוזת הקרובה ביותר, היא קשה לפתרון, אך הצלחנו למצוא אלגוריתמים יעילים למספר מחרוזות לא גדול.